package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020/12/31 下午7:16
 *
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 */
public class _124_二叉树中的最大路径和 {

    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {

        if (root == null) {

            return 0;
        }

        maxVal(root);
        return max;
    }

    private int maxVal(TreeNode node) {

        if (node == null) {

            return 0;
        }

        int leftVal = maxVal(node.left);
        int rightVal = maxVal(node.right);

        int p = Math.max(Math.max(leftVal + node.val,rightVal + node.val),node.val);

        int levelMax;
        if (node.left != null && node.right != null) {

            levelMax = Math.max(Math.max(leftVal, rightVal), leftVal+rightVal+node.val);
        }else if (node.right == null && node.left == null) {

            levelMax = node.val;
        } else if (node.left == null) {

            levelMax = Math.max(rightVal,rightVal+node.val);
        }else {

            levelMax = Math.max(leftVal,leftVal+node.val);
        }

        max = Math.max(max, Math.max(p,levelMax));
        return p;
    }

}
